/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

/**
 * @author zhong
 *
 */
public class LargestPlusSign {
	public int orderOfLargestPlusSignDP(int N, int[][] mines) {
		HashSet<Integer> zeros = new HashSet<>(mines.length);
		for (int[] is : mines) {
			int rep = is[0] * N + is[1];
			zeros.add(rep);
		}
		int[][] dp = new int[N][N];
		for (int i = 0; i < N; i++) {
			int count = 0;
			for (int j = 0; j < N; j++) {
				if (zeros.contains(i * N + j)) {
					count = 0;
				} else {
					dp[i][j] = ++count;
				}
			}
			count = 0;
			for (int j = N - 1; j >= 0; j--) {
				if (zeros.contains(i * N + j)) {
					count = 0;
				} else {
					dp[i][j] = Math.min(dp[i][j], ++count);
				}
			}
		}
		int ans = 0;
		for (int j = 0; j < N; j++) {
			int count = 0;
			for (int i = 0; i < N; i++) {
				if (zeros.contains(i * N + j)) {
					count = 0;
				} else {
					dp[i][j] = Math.min(dp[i][j], ++count);
				}
			}
			count = 0;
			for (int i = N - 1; i >= 0; i--) {
				if (zeros.contains(i * N + j)) {
					count = 0;
				} else {
					dp[i][j] = Math.min(dp[i][j], ++count);
					ans = Math.max(ans, dp[i][j]);
				}
			}
		}
		return ans;
	}

	public int orderOfLargestPlusSign(int N, int[][] mines) {
		// 设计一种机制，方便的查找对应位置是0
		HashSet<Integer> zeros = new HashSet<>(mines.length);
		for (int[] is : mines) {
			int rep = is[0] * N + is[1];
			zeros.add(rep);
		}

		//
		ArrayList<ArrayList<int[]>> rows = new ArrayList<>();
		for (int i = 0; i < N; i++) {// 每一行
			ArrayList<int[]> intervals = new ArrayList<>();
			int rep = i * N;// 数字表示
			int j = 0;
			while (j < N) {
				while (j < N && zeros.contains(rep + j)) {// 跳过0
					j++;
				}
				if (j == N) {
					break;
				}
				int start = j;
				while (j < N && !zeros.contains(rep + j)) {// 连续的1
					j++;
				}
				intervals.add(new int[] { start, j - 1 });
			}
			rows.add(intervals);
		}

		ArrayList<ArrayList<int[]>> cols = new ArrayList<>();
		for (int j = 0; j < N; j++) {// 每一列
			ArrayList<int[]> intervals = new ArrayList<>();
			int i = 0;
			while (i < N) {
				while (i < N && zeros.contains(i * N + j)) {
					i++;
				}
				if (i == N) {
					break;
				}
				int start = i;
				while (i < N && !zeros.contains(i * N + j)) {
					i++;
				}
				intervals.add(new int[] { start, i - 1 });
			}
			cols.add(intervals);
		}

		int maxO = 0;
		for (int i = 0; i < N; i++) {
			for (int[] intval : rows.get(i)) {
				int s = intval[0];
				int e = intval[1];
				for (int j = s; j <= e; j++) {
					int len = Math.min(j - s + 1, e - j + 1);
					if (len <= maxO)
						continue;
					ArrayList<int[]> colCVals = cols.get(j);// 找第j列的包含当前节点的区间
					int index = Collections.binarySearch(colCVals, new int[] { i, 0 }, (a, b) -> (a[0] - b[0]));
					if (index < 0) {
						index = -index - 1;
						index--;
					}
					int[] inval = colCVals.get(index);
					// 找到该区间对当前中心点的长度
					len = Math.min(len, i - inval[0] + 1);
					len = Math.min(len, inval[1] - i + 1);
					maxO = Math.max(maxO, len);
				}
			}
		}
		return maxO;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int N = 5;
		int[][] mines = {};
		System.out.println(new LargestPlusSign().orderOfLargestPlusSign(N, mines));
		System.out.println(new LargestPlusSign().orderOfLargestPlusSignDP(N, mines));
	}

}
